Computer assisted design (CAD) tools have been developed for laying out integrated circuit implementations of boolean expressions. For example, there are CAD tools for disjunctively decomposing boolean expressions into a sum of products form for generating programmable logic array (PLA) very large scale integrated (VLSI) circuit implementations of various functions. As is known, any boolean expression can be decomposed into a sum of products, but the decomposition is unqieu only if each of the products contains all of the variables. Techniques have been developed for minimizing the number of product terms which are required to provide a unique representation, so relatively compact PLAs may be designed to perform tasks ranging from relatively simple counter and decoder functions to far more complex controller and table look-up memory functions. The disjunctive representation of boolean expressions also is utilized to some extent in the design of so-called Weinberger's arrays.
Another known process for decomposing boolean expressions allows any expression of N variables to be represented by two partial functions of N-1 variables, with a boolean choice operator between the partial functions, such that: EQU F[x.sub.1,x.sub.2, . . . , x.sub.n ]=x.sub.1 .multidot.F.sub.1 [x.sub.2, . . . , x.sub.n ]+.about.x.sub.1 .multidot.F.sub.0 x.sub.2, . . . , x.sub.n ](1)
where:
".multidot." represents the AND (product) operator, PA1 "+" represents the OR (sum) operator, and PA1 ".about." represents the NOT (complement or negation) operator
An IF operator (i.e., a conceptual multiplexor) for selecting one of two subexpressions can be defined in terms of the AND and OR operators as follows: EQU IF[a,b,c]=a.multidot.b+.about.a.multidot.c. (2)
Thus, equation (1) can be rewritten as an IF function: EQU F[x.sub.1,x.sub.2, . . . , x.sub.n ]=IFx.sub.1 THENF.sub.1 [x.sub.2, . . . , x.sub.n ]ELSEF.sub.0 [x.sub.2, . . . , x.sub.n ] (3)
which simplifies to: EQU F[x.sub.1,x.sub.2, . . . , x.sub.n ]=IF{x.sub.1,F.sub.1 [x.sub.2, . . . , x.sub.n ], F.sub.0 [x.sub.2, . . . , x.sub.n ]} (4)
Assuming that the variables are ordered, equation (4) may be abbreviated as: EQU F=x.multidot.F.sub.1 +.about.x.multidot.F.sub.0. (5)
This simplified representation is sometimes referred to as a binary decision tree. See, for example, Akers, Sheldon, "Binary Decision Diagrams," IEEE Transactions on Computers, Vol. C-27, No. 6, June 1978, pp. 509-516.
Binary decision trees are easy to operate upon, and the composition laws which govern them are straightforward. Heretofore, lower, they have not been widely utilized for laying out integrated circuit (e.g., VLSI) implementations of boolean expressions because the size of the representation which they conventionally yield for an expression containing N variables is 2.sup.N. As a general rule, size is the most important parameter of a representation because the layout area required for the representation and the computational time required for it to perform its intended function both usually increase as a function of the size of the representation.